{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #GCD Sort of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #math #number-theory #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #数学 #数论 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: gcdSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最大公因数排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，你可以在 <code>nums</code> 上执行下述操作 <strong>任意次</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>gcd(nums[i], nums[j]) &gt; 1</code> ，交换 <code>nums[i]</code> 和 <code>nums[j]</code> 的位置。其中 <code>gcd(nums[i], nums[j])</code> 是&nbsp;<code>nums[i]</code> 和 <code>nums[j]</code> 的最大公因数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果能使用上述交换方式将 <code>nums</code> 按 <strong>非递减顺序</strong> 排列，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [7,21,3]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以执行下述操作完成对 [7,21,3] 的排序：\n",
    "- 交换 7 和 21 因为 gcd(7,21) = 7 。nums = [<em><strong>21</strong></em>,<em><strong>7</strong></em>,3]\n",
    "- 交换 21 和 3 因为 gcd(21,3) = 3 。nums = [<em><strong>3</strong></em>,7,<em><strong>21</strong></em>]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,2,6,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法完成排序，因为 5 不能与其他元素交换。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [10,5,9,3,15]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "可以执行下述操作完成对 [10,5,9,3,15] 的排序：\n",
    "- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [<em><strong>15</strong></em>,5,9,3,<em><strong>10</strong></em>]\n",
    "- 交换 15 和 3 因为 gcd(15,3) = 3 。nums = [<em><strong>3</strong></em>,5,9,<em><strong>15</strong></em>,10]\n",
    "- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,<em><strong>10</strong></em>,<em><strong>15</strong></em>]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [gcd-sort-of-an-array](https://leetcode.cn/problems/gcd-sort-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [gcd-sort-of-an-array](https://leetcode.cn/problems/gcd-sort-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,21,3]', '[5,2,6,2]', '[10,5,9,3,15]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = list(range(n))\n",
    "        self.ranks = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        while self.parents[x] != x:\n",
    "            x = self.parents[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        x_parent = self.parents[x]\n",
    "        y_parent = self.parents[y]\n",
    "        if x_parent == y_parent:\n",
    "            return False\n",
    "        if self.ranks[x_parent] > self.ranks[y_parent]:\n",
    "            self.parents[y_parent] = x_parent\n",
    "        elif self.ranks[x_parent] > self.ranks[y_parent]:\n",
    "            self.parents[x_parent] = y_parent\n",
    "        else:\n",
    "            self.parents[x_parent] = y_parent\n",
    "            self.ranks[y_parent] += 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        uf_set = UnionFind(100001)\n",
    "        for n in nums:\n",
    "            a = 2\n",
    "            while a * a <= n:\n",
    "                if n % a == 0:\n",
    "                    uf_set.union(n, a)\n",
    "                    uf_set.union(n, n // a)\n",
    "                a += 1\n",
    "        res = True\n",
    "        for a, b in zip(nums, sorted(nums)):\n",
    "            if uf_set.find(a) != uf_set.find(b):\n",
    "                res = False\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.components = n\n",
    "        self.fa = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        return \" \".join(map(str, self.fa))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fy] > self.rank[fx]:\n",
    "            fx, fy = fy, fx\n",
    "        self.fa[fy] = fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.components -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def all_is_connected(self):\n",
    "        return self.components == 1\n",
    "\n",
    "    def size(self, x):\n",
    "        return self.rank[self.find(x)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = max(nums) + 1\n",
    "        uf = UnionFind(N)\n",
    "\n",
    "        for x in nums:\n",
    "            i = 2\n",
    "            y = x\n",
    "            # merge x to it's primes\n",
    "            while i * i <= x:\n",
    "                if x % i == 0:\n",
    "                    uf.union(y, i)\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                uf.union(y, x)\n",
    "\n",
    "        for x, y in zip(nums, sorted(nums)):\n",
    "            # print(x, y, uf)\n",
    "            if not uf.is_connected(x, y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = 10 ** 5 + 1\n",
    "        UF = UnionFind(N)\n",
    "\n",
    "        n = len(nums)\n",
    "        for x in nums:\n",
    "            a = 2\n",
    "            while a * a <= x:\n",
    "                if x % a == 0:\n",
    "                    b = x // a\n",
    "                    UF.Union(x, a)\n",
    "                    UF.Union(x, b)\n",
    "                a += 1\n",
    "                \n",
    "        tar = sorted(nums)\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            y = tar[i]\n",
    "            if UF.connected(x, y) == False:\n",
    "                return False\n",
    "        return True\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\r\n",
    "    def __init__(self, n: int):\r\n",
    "        self.parent = [x for x in range(n)]\r\n",
    "        self.size = [1 for x in range(n)]\r\n",
    "    \r\n",
    "    def Find(self, x: int) -> int:\r\n",
    "        if self.parent[x] != x:\r\n",
    "            self.parent[x] = self.Find(self.parent[x])\r\n",
    "        return self.parent[x]\r\n",
    "    \r\n",
    "    def Union(self, x: int, y: int) -> bool:\r\n",
    "        root_x = self.Find(x)\r\n",
    "        root_y = self.Find(y)\r\n",
    "        if root_x == root_y:\r\n",
    "            return False\r\n",
    "        if self.size[root_x] > self.size[root_y]:\r\n",
    "            root_x, root_y = root_y, root_x\r\n",
    "        self.parent[root_x] = root_y\r\n",
    "        self.size[root_y] += self.size[root_x]\r\n",
    "        return True\r\n",
    "\r\n",
    "    def connected(self, x: int, y: int) -> bool:\r\n",
    "        return self.Find(x) == self.Find(y)\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\r\n",
    "        N = 10 ** 5 + 1\r\n",
    "        UF = UnionFind(N)\r\n",
    "\r\n",
    "        n = len(nums)\r\n",
    "        for x in nums:\r\n",
    "            a = 2\r\n",
    "            while a * a <= x:\r\n",
    "                if x % a == 0:\r\n",
    "                    b = x // a\r\n",
    "                    UF.Union(x, a)\r\n",
    "                    UF.Union(x, b)\r\n",
    "                a += 1\r\n",
    "                \r\n",
    "        tar = sorted(nums)\r\n",
    "        for i in range(n):\r\n",
    "            x = nums[i]\r\n",
    "            y = tar[i]\r\n",
    "            if UF.connected(x, y) == False:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = 10 ** 5 + 1\n",
    "        UF = UnionFind(N)\n",
    "\n",
    "        n = len(nums)\n",
    "        for x in nums:\n",
    "            a = 2\n",
    "            while a * a <= x:\n",
    "                if x % a == 0:\n",
    "                    b = x // a\n",
    "                    UF.Union(x, a)\n",
    "                    UF.Union(x, b)\n",
    "                a += 1\n",
    "                \n",
    "        tar = sorted(nums)\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            y = tar[i]\n",
    "            if UF.connected(x, y) == False:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = 10 ** 5 + 1\n",
    "        UF = UnionFind(N)\n",
    "\n",
    "        n = len(nums)\n",
    "        for x in nums:\n",
    "            a = 2\n",
    "            while a * a <= x:\n",
    "                if x % a == 0:\n",
    "                    b = x // a\n",
    "                    UF.Union(x, a)\n",
    "                    UF.Union(x, b)\n",
    "                a += 1\n",
    "                \n",
    "        tar = sorted(nums)\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            y = tar[i]\n",
    "            if UF.connected(x, y) == False:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        N = 10 ** 5 + 1\n",
    "        UF = UnionFind(N)\n",
    "\n",
    "        n = len(nums)\n",
    "        for x in nums:\n",
    "            a = 2\n",
    "            while a * a <= x:\n",
    "                if x % a == 0:\n",
    "                    b = x // a\n",
    "                    UF.Union(x, a)\n",
    "                    UF.Union(x, b)\n",
    "                a += 1\n",
    "                \n",
    "        tar = sorted(nums)\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            y = tar[i]\n",
    "            if UF.connected(x, y) == False:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5 + 1\n",
    "f = [[] for _ in range(N)]\n",
    "for i in range(2, N):\n",
    "    if not f[i]:\n",
    "        for j in range(i, N, i):\n",
    "            f[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            for x in f[v]:\n",
    "                d[x].append(i)\n",
    "\n",
    "        n = len(nums)\n",
    "        fa = list(range(n))\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        for a in d.values():\n",
    "            for i in range(1, len(a)):\n",
    "                fa[find(a[i])] = find(a[0])\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for i,v in enumerate(fa):\n",
    "            g[v].append(i)\n",
    "        \n",
    "        arr = [0] * n\n",
    "        for a in g.values():\n",
    "            b = sorted(nums[i] for i in a)\n",
    "            for i,v in zip(a,b):\n",
    "                arr[i] = v\n",
    "        return all(a <= b for a,b in pairwise(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5 + 1\n",
    "f = [[] for _ in range(N)]\n",
    "for i in range(2, N):\n",
    "    if not f[i]:\n",
    "        for j in range(i, N, i):\n",
    "            f[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            for x in f[v]:\n",
    "                d[x].append(i)\n",
    "\n",
    "        n = len(nums)\n",
    "        fa = list(range(n))\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        for a in d.values():\n",
    "            for i in range(1, len(a)):\n",
    "                fa[find(a[i])] = find(a[0])\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for i,v in enumerate(fa):\n",
    "            g[v].append(i)\n",
    "        \n",
    "        arr = [0] * n\n",
    "        for a in g.values():\n",
    "            b = sorted(nums[i] for i in a)\n",
    "            for i,v in zip(a,b):\n",
    "                arr[i] = v\n",
    "        return all(a == b for a,b in zip(arr, sorted(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def f(x):\n",
    "    ans = []\n",
    "    d = 2\n",
    "    while d * d <= x:\n",
    "        if x % d == 0:\n",
    "            ans.append(d)\n",
    "            while x % d == 0:\n",
    "                x //= d\n",
    "        d += 1\n",
    "    if x != 1:\n",
    "        ans.append(x)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        # 应该是并查集 + 公因子分解\n",
    "        n = len(nums)\n",
    "        p = [i for  i in range(n)]\n",
    "        m = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            for v in f(x):\n",
    "                m[v].append(i)\n",
    "                \n",
    "        def find(node):\n",
    "            while p[node] != node:\n",
    "                p[node] = p[p[node]]\n",
    "                node = p[node]\n",
    "            return node\n",
    "\n",
    "        def union(a, b):\n",
    "            root_a, root_b = find(a), find(b)\n",
    "            if root_a != root_b:\n",
    "                p[root_a] = root_b\n",
    "            \n",
    "        for k in m:\n",
    "            for v in m[k]:\n",
    "                union(m[k][0], v)\n",
    "        \n",
    "        ans = [find(i) for i in range(n)]\n",
    "        m = defaultdict(list)\n",
    "        for i, x in enumerate(ans):\n",
    "            m[x].append(i)\n",
    "        \n",
    "        arr = nums.copy()\n",
    "        for k in m:\n",
    "            a = sorted([nums[i] for i in m[k]])\n",
    "            for i, x in zip(m[k], a):\n",
    "                arr[i] = x\n",
    "        \n",
    "        return arr == sorted(arr)\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "\n",
    "        mx=max(nums)+1\n",
    "        parent=list(range(mx))\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            a,b=find(x),find(y)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "\n",
    "        for v in nums:\n",
    "            i=2\n",
    "            while i*i<=v:\n",
    "                if v%i==0:\n",
    "                    union(v,i)\n",
    "                    union(v,v//i)\n",
    "                i+=1\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            root=find(v)\n",
    "            g[root].append(i)\n",
    "        \n",
    "\n",
    "        \n",
    "        for k,v in g.items():\n",
    "            arr=[nums[i] for i in v]\n",
    "            arr.sort()\n",
    "            for i,j in zip(v,arr):\n",
    "                nums[i]=j\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1]<nums[i]:return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "\n",
    "        mx=max(nums)+1\n",
    "        parent=list(range(mx))\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            a,b=find(x),find(y)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "                \n",
    "        st=set(nums)\n",
    "        for i in range(2,mx):\n",
    "            for j in range(i,mx,i):\n",
    "                if j in st:\n",
    "                    union(i,j)\n",
    "\n",
    "        g=defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            root=find(v)\n",
    "            g[root].append(i)\n",
    "        \n",
    "\n",
    "        \n",
    "        for k,v in g.items():\n",
    "            arr=[nums[i] for i in v]\n",
    "            arr.sort()\n",
    "            for i,j in zip(v,arr):\n",
    "                nums[i]=j\n",
    "        \n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1]<nums[i]:return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def breakdown(num):\n",
    "    i = 2\n",
    "    res = []\n",
    "    while i * i <= num:\n",
    "        if num % i == 0:\n",
    "            res.append(i)\n",
    "            while num % i == 0:\n",
    "                num //= i\n",
    "        i += 1\n",
    "    if num > 1:\n",
    "        res.append(num)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sorted(nums)\n",
    "        \n",
    "        # 父节点数组\n",
    "        fa = list(range(max(nums) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for x in breakdown(num):\n",
    "                union(num, x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if find(s[i]) != find(nums[i]):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "breakdown.cache_clear()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def breakdown(num):\n",
    "    i = 2\n",
    "    res = []\n",
    "    while i * i <= num:\n",
    "        if num % i == 0:\n",
    "            res.append(i)\n",
    "            while num % i == 0:\n",
    "                num //= i\n",
    "        i += 1\n",
    "    if num > 1:\n",
    "        res.append(num)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sorted(nums)\n",
    "        \n",
    "        # 父节点数组\n",
    "        fa = list(range(max(nums) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for x in breakdown(num):\n",
    "                union(num, x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if find(s[i]) != find(nums[i]):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:#并查集模板\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        pa, pb = self.find(a), self.find(b)\n",
    "        if pa != pb:\n",
    "            if self.size[pa] >= self.size[pb]:\n",
    "                self.size[pa] += self.size[pb]\n",
    "                self.p[pb] = pa\n",
    "            else:\n",
    "                self.size[pb] += self.size[pa]\n",
    "                self.p[pa] = pb\n",
    "\n",
    "def f(x):\n",
    "    ans = set()\n",
    "    if x % 2 == 0:\n",
    "        ans.add(2)\n",
    "        while x % 2 == 0:\n",
    "            x //= 2\n",
    "    d = 3\n",
    "    while d ** 2 <= x:\n",
    "        if x % d == 0:\n",
    "            ans.add(d)\n",
    "            while x % d == 0:\n",
    "                x //= d\n",
    "        d += 2\n",
    "    if x > 1: ans.add(x)\n",
    "    return ans\n",
    "\n",
    "mx = 10 ** 5\n",
    "myPrimes = [set()] * (mx + 1)\n",
    "for i in range(2, mx + 1):\n",
    "    myPrimes[i] = f(i)\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        uf = UnionFind(n + max(nums) + 1)\n",
    "        idx = dict()\n",
    "        for i, j in enumerate(nums):\n",
    "            idx[j] = i\n",
    "            for p in myPrimes[j]:\n",
    "                uf.union(i, p + n)\n",
    "        target = sorted(nums)\n",
    "        for i, j in enumerate(target):\n",
    "            if uf.find(i) != uf.find(idx[j]):\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def breakdown(num):\n",
    "    i = 2\n",
    "    res = []\n",
    "    while i * i <= num:\n",
    "        if num % i == 0:\n",
    "            res.append(i)\n",
    "            while num % i == 0:\n",
    "                num //= i\n",
    "        i += 1\n",
    "    if num > 1:\n",
    "        res.append(num)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def gcdSort(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        s = sorted(nums)\n",
    "        \n",
    "        # 父节点数组\n",
    "        fa = list(range(max(nums) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            for x in breakdown(num):\n",
    "                union(num, x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if find(s[i]) != find(nums[i]):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
